Chihik's Blog

Chihik's Blog

UVA1218 Perfect Service

发布于 2020-10-14 | 分类于 树形dp | 4分钟 | 584字数

一道很不错的树形dp。

令 dp[u][f]dp[u][f] 为以uu为根的子树。

f=0f=0，表示uu为服务器，那么uu的儿子和父亲既可以是服务器，也可以不是。

阅读全文 »

CF767C Garland

发布于 2020-10-14 | 分类于 树形dp | 2分钟 | 321字数

首先可以确定的是，如果点权和不为3的倍数，一定不存在合法方案。

记所有点权和为sumsum。

容易想到，令 dp[u]dp[u] 表示以 uu 为根的子树的点权和 ， 则有转移：

阅读全文 »

SP9934 ALICE - Alice and Bob

发布于 2020-09-28 | 分类于 博弈论 | 3分钟 | 477字数

这道题的状态挺难设计的。。。

令 ss 为石子的总数，那么操作次数最多为 s+(n−1)s+(n-1)

如果石子数量全不为一，那么先手必胜的条件为 s+(n−1)s+(n-1) 为奇数，因为他一定可以保证操作 s+(n−1)s+(n-1) 次。

阅读全文 »

UVA1500 Alice and Bob

发布于 2020-09-28 | 分类于 博弈论 | 3分钟 | 477字数

这道题的状态挺难设计的。。。

令 ss 为石子的总数，那么操作次数最多为 s+(n−1)s+(n-1)

如果石子数量全不为一，那么先手必胜的条件为 s+(n−1)s+(n-1) 为奇数，因为他一定可以保证操作 s+(n−1)s+(n-1) 次。

阅读全文 »

P4056 [JSOI2009]火星藏宝图

发布于 2020-09-23 | 分类于 斜率优化 | 3分钟 | 472字数

首先有一个非常 naive 的 O(n2)\mathcal{O(n^2)} dp。

令 dpidp_i 表示到第 ii 座岛的最大收益，那么有：

dpi=max⁡1≤j≤n,j=i,xj≤xi,yj≤yi{dpj−(xi−xj)2−(yi−yj)2}+vidp_i=\max_{1\le j \le n, j \not= i ,x_j \le x_i ,y_j \le y_i }\{dp_j-(x_i-x_j)^2-(y_i-y_j)^2\}+v_i

阅读全文 »

P2120 [ZJOI2007]仓库建设

发布于 2020-09-23 | 分类于 斜率优化 | 3分钟 | 429字数

令 did_i 为工厂 ii 到工厂 nn （山底）的距离， dpidp_i 为在第 ii 个工厂建仓库的最小花费。

因为只能向下运，所以第 nn 个工厂必须建仓库存放它自己的产品，答案便为 dpndp_n

边界条件 dp0dp_0 为不建仓库的花费。

阅读全文 »

P3648 [APIO2014]序列分割

发布于 2020-09-23 | 分类于 斜率优化 | 3分钟 | 436字数

dp[t][i]=max⁡{dp[t−1][j]+sj(si−sj)}dp[t][i]=\max\{dp[t-1][j] + s_j(s_i-s_j)\}

dp[t][i]=max⁡{dp[t−1][j]+sjsi−sj2}dp[t][i]=\max\{dp[t-1][j] + s_js_i-s_j^2\}

阅读全文 »
0%